const int N = 1e6, M = 1e6 + 10;
int tnt = 0;
int arr[N + 9];
int root[N + 9];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct kkk{
    int l,r,val;
}tr[25000010];
int build(int node,int l,int r)
{
    node = ++tnt;
    if(l == r)
    {
        tr[node].val = arr[l];
        return tnt;
    }
    int mid = l + r >> 1;
    tr[node].l = build(tr[node].l,l,mid);
    tr[node].r = build(tr[node].r,mid + 1,r);
    return node;

}
int clone(int node)
{
    tnt++;
    tr[tnt] = tr[node];//全部信息传新的节点
    return tnt;
}
int update(int node,int l,int r,int x,int val)
{
    node = clone(node);//更新要新建节点
    if(l == r)
    {
        tr[node].val = val;
    }
    else
    {
        int mid = l + r >> 1;
        if(x <= mid)
        {
            tr[node].l = update(tr[node].l,l,mid,x,val);
        }
        else
        {
            tr[node].r = update(tr[node].r,mid + 1,r,x,val);
        }
    }
    return node;

}
int query(int node,int l,int r,int x)
{
    if(l == r)
    {
        return tr[node].val;
    }
    else
    {
        int mid = l + r >> 1;
        if(x <= mid)
        {
            return query(tr[node].l,l,mid,x);
        }
        else
        {
            return query(tr[node].r,mid + 1,r,x);
        }
    }
}
void solve()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> arr[i];

    root[0] = build(0,1,n);

    for(int i = 1; i <= m; i ++)
    {
        int v,mode,x;
        cin >> v >> mode >> x;
        if(mode == 1)
        {
            int y;
            cin >> y;
            root[i] = update(root[v],1,n,x,y);
        }
        else
        {
            cout << query(root[v],1,n,x) << endl;
            root[i] = root[v];
        }
    }
}
